package com.hanxiaozhang.no3algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈最大子字段和〉
 * <p>
 * 输入一个整型数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，
 * 每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
 * 例如：输入的数组为[1,-2,3,10,-4,7,2,-5]，和最大的子数组为[3,10,-4,7,2]，
 * 因此：输出为该子数组的和18。
 *
 * @author hanxinghua
 * @create 2023/11/5
 * @since 1.0.0
 */
public class No2MaxSubArraySum {

    public static void main(String[] args) {

        int[] arrays = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        method1(arrays);
        method2(arrays);
        // 记住
        method3(arrays);
    }


    /**
     * 动态规划算法
     *
     * @param a
     * @return
     */
    private static int method3(int[] a) {

        int max = 0;

        // 1.定义记忆化表（定义状态）：其长度和arrays一致，用于存储"以每一个元素结尾子段"的最大子段和。
        int[] b = new int[a.length];

        // 2. 初始化：记忆化表中的边界条件值初始化
        b[0] = a[0];

        // 3. 构建状态转移方程：
        // 前提条件：i > 0   =>  因为0是边界条件值
        // 情况1：加上之前 i -1 元素的最大字段和  => b[i-1] + a[i]
        // 情况2：不加上之前 i -1 元素的最大字段和 => a[i]
        // 汇总：max（情况1,情况2） => max（b[i-1]+a[i],a[i]）

        // 4. 选择最优子结构（根据记忆表的值，计算每一步的最优值）
        for (int i = 1; i < a.length; i++) {

            b[i] = Math.max(b[i - 1] + a[i], a[i]);
            // 5.回溯求解（遍历记忆表，找出最优解）
            if (b[i] > max) {
                max = b[i];
            }
        }
        System.out.println("max is " + max);
        return max;
    }


    /**
     * 动态规划算法
     * <p>
     * 记录开始位置，结束位置。
     *
     * @param a
     * @return
     */
    private static int method2(int[] a) {

        int max = 0, start = 0, end = 0;

        // 1.定义记忆化表（定义状态）：其长度和arrays一致，用于存储"以每一个元素结尾子段"的最大子段和。
        int[] b = new int[a.length];

        // 2. 初始化：记忆化表中的边界条件值初始化
        b[0] = a[0];

        // 3. 构建状态转移方程：
        // 前提条件：i > 0   =>  因为0是边界条件值
        // 情况1：加上之前 i -1 元素的最大字段和  => b[i-1] + a[i]
        // 情况2：不加上之前 i -1 元素的最大字段和 => a[i]
        // 汇总：max（情况1,情况2） => max（b[i-1]+a[i],a[i]）

        // 4. 选择最优子结构（根据记忆表的值，计算每一步的最优值）
        for (int i = 1; i < a.length; i++) {

            if (b[i - 1] + a[i] > a[i]) {
                b[i] = b[i - 1] + a[i];
            } else {
                b[i] = a[i];
                start = i;
            }

            // 5.回溯求解（遍历记忆表，找出最优解）
            if (b[i] > max) {
                max = b[i];
                end = i;
            }
        }
        System.out.println("max is " + max + " ,start is " +
                start + " ,end is " + end + " ,subArray is " +
                Arrays.toString(Arrays.copyOfRange(a, start, end + 1)));
        return max;
    }


    /**
     * 暴力破解
     *
     * @param arrays
     */
    private static void method1(int[] arrays) {
        int max = 0, start = 0, end = 0, temp = 0;
        for (int i = 0; i < arrays.length; i++) {
            for (int j = i; j < arrays.length; j++) {
                temp += arrays[j];
                if (temp > max) {
                    max = temp;
                    start = i;
                    end = j;
                }
            }
            temp = 0;
        }
        System.out.println("max is " + max + " ,start is " +
                start + " ,end is " + end + " ,subArray is " +
                Arrays.toString(Arrays.copyOfRange(arrays, start, end + 1)));
    }

}
